//110 Balanced Binary Tree
/*
判断一个二叉树是否平衡。树平衡的定义是，二叉树的每个节点的左右子树的高度差的绝对值不超过 1 ，则二叉树是平衡二叉树

输入：root = [3,9,20,null,null,15,7]
输出：true

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false


*/

// 主函数
bool isBalanced(TreeNode *root)
{
	return helper(root) != -1;
}
// 辅函数
int helper(TreeNode *root)
{
	if (!root)
	{
		return 0;
	}

	//
	int left = helper(root->left), right = helper(root->right);

	//
	if (left == -1 || right == -1 || abs(left - right) > 1)
	{
		return -1;
	}
	return 1 + max(left, right);
}

//方法一：自顶向下的递归
class Solution
{
public:
	int height(TreeNode *root)
	{
		if (root == NULL)
		{
			return 0;
		}
		else
		{
			return max(height(root->left), height(root->right)) + 1;
		}
	}

	bool isBalanced(TreeNode *root)
	{
		if (root == NULL)
		{
			return true;
		}
		else
		{
			return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
		}
	}
};

//方法二：自底向上的递归
class Solution
{
public:
	int height(TreeNode *root)
	{
		if (root == NULL)
		{
			return 0;
		}
		int leftHeight = height(root->left);
		int rightHeight = height(root->right);
		if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
		{
			return -1;
		}
		else
		{
			return max(leftHeight, rightHeight) + 1;
		}
	}

	bool isBalanced(TreeNode *root)
	{
		return height(root) >= 0;
	}
};
